/* -*-jde-*- */
/* <Coloring.java> */
package Practica8.graphs;

import Practica8.util.Graph;

/**
 * Cualquier objeto que implemente esta interfaz debera encontrar una coloración
 * en una gráfica
 *
 * @author Peralta Santa Anna Victor Miguel
 * @since  Noviembre 2011
 */
public interface Coloring {

    /**
     * Da una coloración con un algoritmo no deterministico polinomial para <i>G</i>.
     *
     * La coloración es con tantos colores como colorNumber
     * La coloración se debe de hacer en O(|V|)
     *
     * @param graph La grafica.
     * @param colorNumber el numero de colores
     * @return la gráfica coloreada
     */
    public Graph getColoring(Graph graph, int colorNumber);

    /**
     * Devuelve verdadero si y solo sí la gráfica esta correctamente coloreada.
     * 
     * La verificación se debe de hacer en a lo más O(|V|^2)
     * @param graph la gráfica a verificar.
     * @return <code>true</code> si la grafica esta bien coloreada <code>false</code> en otro caso
     */
    public boolean isRightColored(Graph graph);
}
